The internet has revolutionized the movement of information for both commercial and personal business. Fantastic technical advances in the communications arts have fueled the tremendous growth of the internet and networking in general. The growth fueled by these advances has in turn become a catalyst for greater innovation.
One area receiving a great deal of attention is the routing, or switching of information among various networks, or different segments of a network. The devices which perform these operations are typically known as routers or switches.
A principal function of a router or a switch is to move information, usually in the form of packets, particularly Internet Protocol, or IP, packets, from one network, or segment of a network, to another. The different networks or segments may frequently be of different types of media, e.g., coaxial cable versus fiber optics, and may often be of differing data rates or capacity. Often, the different network segments go to different physical locations, for example, different parts of a building, or distinct geographical regions. Frequently, too, information destined for multiple networks or segments may be received from a single network or segment.
Consequently, sending data to the right network or segment, along with controlling the flow, e.g., not attempting to send more data to a network or segment that it can handle, are of critical importance in the function of a network router or switch.
Receiving packets into a queue, and sending them out when a receiving network or segment is capable of accommodating such packets is a well known method of controlling the flow.
In the prior art, it is well known to request an allocation or space in a receiving queue associated with a receiving network or segment. This request is commonly known as a memory or buffer request. When a buffer for a receiving network or segment is able to actually receive a packet, it typically sends a message to the sending function to indicate its readiness. This reply is known as a memory or buffer reply. In response to such a buffer reply, a sending function transfers a packet to a receiving function associated with an outbound network or segment of a network.
FIG. 1 illustrates a prior art sequence of processing a packet. Packets are received and temporarily stored in a queue 100. When a packet, for example packet 0 (110) reaches the head of queue 102, it is ready to be forwarded. After packet 0 (110) has been successfully forwarded, packet 1 (111 ) will move to the head of the queue, and so on.
The mechanism of queue 100 ensures that packets are forwarded in the order in which they are received. Many types of multi part messages, for example streaming audio, may be severely degraded if their original packet order is not maintained throughout transmission. Further, processing packets in order ensures the equitable allocation of fixed resources within a network device or among networks. For example, if a packet processing device forwarded a packet to any receiver that was ready, as opposed to forwarding packets in order, a high bandwidth receiver could effectively monopolize the resources of the forwarding packet processing device to the detriment of packets intended for other, slower receivers. Such packets could enter a detrimental state of suspension, even if the receiving network had available bandwidth. For these reasons and others, processing packets in order is considered a critical attribute for switches and routers.
Still referring to FIG. 1, when packet 0 (110) reaches the head of queue 102 position, a buffer request 0 (120) is generated and sent to a receiving buffer (not shown). The receiving buffer, in general, will be busy, for example receiving packets from other sources or sending packets out via an associated network interface. Consequently, there will typically be a period of latency 122 prior to the receiving buffer's readiness to receive a packet.
After period of latency 122, when it is ready, a receiving buffer will reply to buffer request 0 (120) with a buffer reply 0 (124) message, indicating that it is ready to receive packet 0 (110). Upon receiving buffer reply 0 (124), packet 0 (110) is sent to the receiving buffer.
After packet 0 (110) has been successfully sent to a receiving buffer, packet 1 (111) moves to the head of queue 100, and the process repeats. As shown in FIG. 1, buffer request 1 (130) is not sent until packet 0 (110) has completed being sent. There will typically be a latency period 132, which in general is a different amount of time that latency period 122, followed by a buffer reply 1 (134) and ultimately the sending of packet 1 (111), which is not shown.
Unfortunately, in the prior art, the sequence of sending a buffer request, waiting until a receiving buffer is ready, receiving a buffer reply, and sending the designated packet requires an undesirably long time to complete. A packet would not be sent until a corresponding buffer reply was received. A second cycle of sending a buffer request, receiving a buffer reply, and sending a designated packet would not be initiated until after a current request, reply and transfer cycle has successfully completed. This restriction has a desired effect of sending packets in proper order, but imposes a severe latency penalty. In the prior art, this latency period 122 is lost. The latency effectively reduces overall bandwidth within the router or switch, which in turn reduces the number of packets it may route or switch on external networks per unit time.